package main

import (
	"errors"
	"flag"
	"fmt"
	"os"
	"syscall"
	"time"
)

func main() {
	input := flag.String("f", "input.txt", "")
	flag.Parse()

	s, err := NewSudoku(*input)
	if err != nil {
		panic(err)
	}
	tStart := time.Now()
	s.Solve()
	useTime := time.Since(tStart)
	s.Print()
	fmt.Printf("计算耗时: %s,尝试次数: %d\n", useTime, s.cnt)
}

const SudokuLineLen = 9 /* 数独长宽都是9 */

type sudoku struct {
	data, org [SudokuLineLen][SudokuLineLen]int
	cnt       int

	setConsoleTextAttribute uintptr
}

func NewSudoku(f string) (*sudoku, error) {
	data, err := os.ReadFile(f)
	if err != nil {
		return nil, err
	}

	var (
		s = &sudoku{
			setConsoleTextAttribute: syscall.NewLazyDLL("kernel32.dll").
				NewProc("SetConsoleTextAttribute").Addr(),
		}
		cnt, i, j int
	)
	const sudokuMaxNumber = SudokuLineLen * SudokuLineLen
	for _, v := range data {
		if v >= '0' && v <= '9' {
			s.data[i][j] = int(v - '0')
			s.org[i][j] = s.data[i][j]

			if cnt++; cnt == sudokuMaxNumber {
				break
			}

			if j < 8 {
				j++
			} else {
				i++
				j = 0
			}
		}
	}

	if cnt < sudokuMaxNumber {
		return nil, errors.New("必须读入81个数字")
	}
	return s, nil
}

func (s *sudoku) Solve() bool {
	for i := 0; i < SudokuLineLen; i++ {
		for j := 0; j < SudokuLineLen; j++ {
			if s.data[i][j] != 0 {
				continue // 跳过原始输入数字
			}

			for k := 1; k <= 9; k++ {
				// 尝试为这个位置放置1-9这些数字,放一次就判断一次是否合法
				if s.IsValidSudoku(i, j, k) {
					s.cnt++ // 尝试放置k的次数

					s.data[i][j] = k // i,j位置放k目前合法
					if s.Solve() {
						return true // 递归下一个可填写位置
					}
					s.data[i][j] = 0 // i,j位置放k不合法,回溯其他解
				}
			}
			// 9个数字都尝试还不行则无解,返回失败避免无限递归
			return false
		}
	}
	// 遍历完没有返回false,则说明找到合适位置的数值
	return true
}

func (s *sudoku) IsValidSudoku(row, col, val int) bool {
	for i := 0; i < 9; i++ {
		if s.data[row][i] == val {
			return false // 同行有重复值
		}
		if s.data[i][col] == val {
			return false // 同列有重复值
		}
	}

	sr, sc := (row/3)*3, (col/3)*3
	for i := sr; i < sr+3; i++ {
		for j := sc; j < sc+3; j++ {
			if s.data[i][j] == val {
				return false // 同一个九宫格有重复值
			}
		}
	}
	return true
}

func (s *sudoku) Print() {
	fmt.Println(" ---------+---------+---------")
	for i := 0; i < SudokuLineLen; i++ {
		for j := 0; j < SudokuLineLen; j++ {
			if j%3 == 0 {
				fmt.Print("|")
			}

			if tmp := s.data[i][j]; tmp > 0 {
				if s.org[i][j] == 0 {
					s.SetConsoleTextAttribute(0x04 | 0x08)
					fmt.Printf(" %d ", tmp)
					s.SetConsoleTextAttribute(0x04 | 0x02 | 0x01)
				} else {
					fmt.Printf(" %d ", tmp)
				}
			} else {
				fmt.Print(" . ")
			}
		}
		if i == SudokuLineLen-1 {
			fmt.Println("|\n ---------+---------+---------")
		} else if (i+1)%3 == 0 {
			fmt.Println("|\n|---------+---------+---------|")
		} else {
			fmt.Println("|\n|         |         |         |")
		}
	}
}

func (s *sudoku) SetConsoleTextAttribute(wAttributes uint16) {
	_, _, _ = syscall.SyscallN(s.setConsoleTextAttribute,
		uintptr(syscall.Stdout), uintptr(wAttributes))
}

/**
* http://cn.sudokupuzzle.org/
* https://www.newdoku.com/zh/sudoku.php
* 上面是2个在线数独网站
* 技巧：http://www.conceptispuzzles.com/zh/index.aspx?uri=puzzle/sudoku/techniques
* 规则：http://www.conceptispuzzles.com/zh/index.aspx?uri=puzzle/sudoku/rules
**/
